package com.zrrd.zuo.class03;

import static com.zrrd.zuo.class01.EasySort.print;

/**
 * @author ywb
 * @Description:
 * @date 2023/3/18 15:21
 */
public class Sort {
    //归并排序
    //1.递归
    public static void  mergeSort(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }
        process(arr,0,arr.length - 1);
    }
public static void process(int[] arr,int L,int R){
    if(L==R){
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr,L,mid);
    process(arr,mid + 1,R);
    merge(arr,L,mid,R);
}
public static void merge(int[] arr,int L,int mid,int R){
    int[] help = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = mid + 1;
    while (p1 <= mid && p2 <= R){
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid){
        help[i++] = arr[p1++];
    }
    while (p2 <= R){
        help[i++] = arr[p2++];
    }
    for ( i = 0; i < help.length; i++) {
        arr[L + i ] = help[i];
    }
}
    //2.非递归
    public static void mergeSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int mergeSize = 1;
        int n = arr.length;
        while (mergeSize < n){
        int L = 0;
        while (L < n){
            int M = L + mergeSize - 1;
            if(M >= n){
                break;
            }
            int R = Math.min(M + mergeSize,n - 1);
            merge(arr,L,M,R);
            L = R + 1;
        }
        if(mergeSize > n/2){
            break;
        }
        mergeSize <<= 1;
        }
    }
    // arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
    //  <arr[R]  ==arr[R]  > arr[R]
    public static int[] netherlandsFlag(int[] arr, int L, int R) {
        if (L > R) {
            return new int[] { -1, -1 };
        }
        if (L == R) {
            return new int[] { L, R };
        }
        int less = L - 1; // < 区 右边界
        int more = R;     // > 区 左边界
        int index = L;
        while (index < more) {
            if (arr[index] == arr[R]) {
                index++;
            } else if (arr[index] < arr[R]) {
                swap(arr, index++, ++less);
            } else { // >
                swap(arr, index, --more);
            }
        }
        swap(arr, more, R);
        return new int[] { less + 1, more };
    }
    //快排
    public static void quickSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process1(arr,0,arr.length - 1);
    }
    public static void process1(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // L..R partition arr[R]  [   <=arr[R]   arr[R]    >arr[R]  ]
        int M = partition(arr, L, R);
        process1(arr, L, M - 1);
        process1(arr, M + 1, R);
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static int partition(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }
        int lessEqual = L - 1;
        int index = L;
        while (index < R) {
            if (arr[index] <= arr[R]) {
                swap(arr, index, ++lessEqual);
            }
            index++;
        }
        swap(arr, ++lessEqual, R);
        return lessEqual;
    }
    //一次搞定相等的一批数
    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    public static void process2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalArea = netherlandsFlag(arr, L, R);
        process2(arr, L, equalArea[0] - 1);
        process2(arr, equalArea[1] + 1, R);
    }
    public static void quickSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process3(arr, 0, arr.length - 1);
    }

    public static void process3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = netherlandsFlag(arr, L, R);
        process3(arr, L, equalArea[0] - 1);
        process3(arr, equalArea[1] + 1, R);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,9,5,7,3,6,34,5,5,3,5,8};
        print(arr);
        quickSort3(arr);
        print(arr);
    }
}
